package lib

import (
	"algorithms/ds"

)

func init() {
	Probs = append(Probs, Problem{
		Num:         298,
		Discription: "二叉树中的最长递增序列",
		Level:       2,
		Labels: map[string]int{
			"二叉树": 1,
			"回溯": 1,
			"递归": 1,
		},
	})
}

func LongestConsecutive2(root *ds.TreeNode) int {
	if root == nil {
		return 0
	}

	res := 0
	var maxLen func(*ds.TreeNode) int
	maxLen = func(node *ds.TreeNode) int {
		length := 1
		subLength := 0
		if node.Left != nil {
			//无论和父节点的值是否递增，都需要递归下来
			leftLength := maxLen(node.Left)
			if node.Left.Val == node.Val+1 {
				subLength = leftLength
			}
		}
		if node.Right != nil {
			rightLength := max(subLength, maxLen(node.Right))
			if node.Right.Val == node.Val+1 {
				subLength = max(subLength, rightLength)
			}
		}
		length += subLength
		res = max(res, length)
		return length
	}

	maxLen(root)
	return res
}